package com.tgy.algorithm.base._二叉树;

import java.util.Stack;


class Info {
    int maxValue;
    int maxRootValue;

    Info(int maxValue,int maxRootValue) {
        this.maxValue = maxValue;
        this.maxRootValue = maxRootValue;
    }
}

public class _二叉树任意节点和的最大值 {

    public static BiTreeNode generalBiTreeNode() {
        /**
         *              1
         *         2           3
         *       4     5    6
         *                 7
         */
        BiTreeNode root = new BiTreeNode(10);
        root.left = new BiTreeNode(-2);
        root.right = new BiTreeNode(1);
        root.left.left = new BiTreeNode(3);
        root.left.left.left = new BiTreeNode(-1);
        root.left.left.right = new BiTreeNode(-2);

        root.left.right = new BiTreeNode(2);

        root.right.left = new BiTreeNode(1);
        root.right.right = new BiTreeNode(2);
        root.right.right.left = new BiTreeNode(1);
        root.right.left.left = new BiTreeNode(-1);
        return root;
    }

    public static void inOrder(BiTreeNode root) {
        if (root == null) {
            return;
        }
        Stack<BiTreeNode> stack = new Stack<>();
        BiTreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            }else {
                node = stack.pop();
                System.out.println(node.val);
                node = node.right;
            }
        }
    }


    public static int maxValue(BiTreeNode root) {

        return doMaxValue(root).maxValue;
    }

    public static Info doMaxValue(BiTreeNode root)  {

        if (root == null)  {
            return null;
        }

        int leftMaxValue = Integer.MIN_VALUE;

        Info leftInfo = doMaxValue(root.left);
        if (leftInfo != null) {
            leftMaxValue = leftInfo.maxValue;
        }

        int rightMaxValue = Integer.MIN_VALUE;
        Info rightInfo = doMaxValue(root.right);
        if (rightInfo != null) {
            rightMaxValue = rightInfo.maxValue;
        }

        int curValue = root.val;
        int curLeftValue = Integer.MIN_VALUE;
        if (leftInfo != null) {
            curLeftValue  = curValue + leftInfo.maxRootValue;
        }

        int curRightValue =  Integer.MIN_VALUE;
        if (rightInfo != null) {
            curRightValue  = curValue + rightInfo.maxRootValue;
        }

        Info info = new Info(0, 0);

        info.maxValue = Math.max(Math.max(leftMaxValue,rightMaxValue),Math.max(curValue,Math.max(curLeftValue,curRightValue)));
        info.maxRootValue = Math.max(curValue,Math.max(curLeftValue,curRightValue));
        return info;
    }

    public static int maxValue01(BiTreeNode root) {

        return doMaxValue01(root).maxValue;
    }

    public static Info doMaxValue01(BiTreeNode root)  {

        if (root == null)  {
            return null;
        }

        int leftMaxValue = Integer.MIN_VALUE;

        Info leftInfo = doMaxValue01(root.left);
        if (leftInfo != null) {
            leftMaxValue = leftInfo.maxValue;
        }

        int rightMaxValue = Integer.MIN_VALUE;
        Info rightInfo = doMaxValue01(root.right);
        if (rightInfo != null) {
            rightMaxValue = rightInfo.maxValue;
        }


        int curValue = root.val;
        int crossCurValue = curValue;

        int curLeftValue = Integer.MIN_VALUE;
        if (leftInfo != null) {
            curLeftValue  = curValue + leftInfo.maxRootValue;
            crossCurValue += leftInfo.maxRootValue;
        }

        int curRightValue =  Integer.MIN_VALUE;
        if (rightInfo != null) {
            curRightValue  = curValue + rightInfo.maxRootValue;
            crossCurValue += rightInfo.maxRootValue;
        }



        Info info = new Info(0, 0);

        info.maxValue = Math.max(Math.max(leftMaxValue,rightMaxValue),Math.max(curValue,Math.max(Math.max(curLeftValue,curRightValue),crossCurValue)));
        info.maxRootValue = Math.max(curValue,Math.max(curLeftValue,curRightValue));
        return info;
    }

    public static int maxLeafToLeaf = Integer.MIN_VALUE;

    public static int leafToLeafMavValue(BiTreeNode  root) {

//        return doLeafToLeafMaxValue(root).maxValue;
        doLeafToLeafMaxValue(root);
        return maxLeafToLeaf;
    }

    public static int doLeafToLeafMaxValue(BiTreeNode root) {

        if (root.left ==  null &&  root.right ==  null)  {
            maxLeafToLeaf = Math.max(maxLeafToLeaf,root.val);
            return root.val;
        }

        int curValue = root.val;
        int leftLeafMax = Integer.MIN_VALUE;
        if (root.left !=  null) {

            leftLeafMax = doLeafToLeafMaxValue(root.left);
            curValue += leftLeafMax;
            leftLeafMax+= root.val;
        }

        int rightLeafMax = Integer.MIN_VALUE;

        if (root.right != null) {
            rightLeafMax =  doLeafToLeafMaxValue(root.right);
            curValue += rightLeafMax;
            rightLeafMax += root.val;
        }
        int retVal = Math.max(leftLeafMax,rightLeafMax);
        maxLeafToLeaf = Math.max(curValue,maxLeafToLeaf);
        return retVal;
    }

    public static void postOrder(BiTreeNode root) {

        Stack<BiTreeNode> stack = new Stack<>();

        BiTreeNode curNode = null;
        BiTreeNode visitedNode = root;
        stack.push(root);

        while (!stack.empty()) {
            curNode = stack.peek();
            if (curNode.left != null && curNode.left != visitedNode &&  curNode.right !=  visitedNode) {
                stack.push(curNode.left);
            }else if(curNode.right != null && curNode.right != visitedNode)  {
                stack.push(curNode.right);
            }else {
                curNode = stack.pop();
                System.out.println(curNode.val);
                visitedNode = curNode;
            }
        }

    }

    public static void main(String[] args) {
        BiTreeNode root = generalBiTreeNode();
//        inOrder(root);
//        int maxValue = maxValue(root);
//        int maxValue = maxValue01(root);
//        System.out.println(maxValue);
//        int maxValue = leafToLeafMavValue(root);
//        System.out.println(maxValue);
        postOrder(root);
    }
}
